This invention relates generally to data compression, and more particularly, to a data compression for a microprocessor system having a cache.
Many modem technologies that use microprocessors or microcontrollers, such as hand-held electronic applications, require high performance processing power combined with highly efficient implementations to reduce system costs and space requirements. The use of instruction caches and data caches in order to improve performance is well known in the industry. In an effort to further reduce system size and cost, it is known to compress instruction data to minimize the amount of memory a system will need. Before an instruction contained in a compressed memory can be used, the information contained within that memory must be decompressed in order for the target data processor to execute.
A prior art method of handling the compression of data for use in a data processor system and the decompression of data for use by that data processor system uses the following steps: dividing the uncompressed program into separate cache blocks; compressing each cache block; and, compacting the individual compressed blocks into a memory. By breaking the program into individual cache blocks, where a cache block represents the number of words in each cache line, it is possible to efficiently compress the data associated with each cache block. Since modem data processing systems generally load an entire cache line at a time, it is possible to fill an entire cache line efficiently by knowing the starting address of a compressed cache block.
The prior art method requires the generation of a look-aside table (LAT). The look-aside table keeps track of which compressed address relates to which cache tag of the data processor. When the instruction pointer of the data processing system requires an address which is not resident within the instruction cache, it is necessary for the data processor system to determine where in compressed memory the required information resides. This information is maintained in the look-aside table stored in the system memory. When a cache miss occurs, the data processor system utilizes a cache refill engine to provide the appropriate information to the next available cache line. The cache refill engine parses the LAT to correlate the new cache tag to the compressed memory. This correlation describes the cache block address, in compressed memory, where the requested instruction resides. Once determined, the compressed memory is accessed, decompressed, and used to fill the appropriate cache line. The cache line containing the newly stored information maintains the original address tag as determined by the instruction pointer for its cache tag. The next time the instruction pointer requests information having the same address tag, a cache hit will occur, indicating the data is in the cache, and processing will continue in a normal fashion, provided the cache line has not been cleared.
In order to reduce the overhead of the cache refill engine having to search through the look-aside table in system memory, it is common for data processor systems to use a compressed cache look-aside buffer CLB.
The CLB maintains a list of recently translated address tags and their corresponding address information in compressed memory. By maintaining an on-chip CLB, overhead associated with parsing the LAT is avoided.
A disadvantage of the prior art system is that it requires a translation of the address tag into the appropriate compressed address location. This is accomplished at the expense of providing and maintaining a CLB, and increasing the complexity of the cache refill engine, which must search a LAT in order to determine the appropriate compressed memory location to access. In addition, it is necessary to perform these functions each time a cache miss occurs. As a result, each cache tag will be re-translated every time it is cleared out of the cache. Therefore, a method, and a data processor, that allows for execution of compressed programs while limiting physical overhead and execution time associated with translation is needed.